The explosion of social networking has led to extensive sharing of information including items such as videos, photos, blogs, links, etc. Existing social networking databases face growing challenges to support highly random writing and reading operations (e.g., new insertion, update and deletion).
Log Structured Merge Tree (LSM) has become a popular solution in many write-optimized databases. AN LSM database typically organizes the data in the storage media in the form of blocks and uses a cache for faster access to recently accessed data. The cache is typically smaller than the entire dataset but has lower latency than the storage media. The LSM database, upon a read request for a data record in a particular data block, pulls in the particular block from the storage media and cache it in memory. However, the cached block may include many data records that are rarely requested. A significant portion of the cache may be wasted in storing these rarely requested data records, resulting in a low cache hit ratio.
Thus, there is a need to improve the efficiency of cache in an LSM database and value in doing so. Solutions to the problem have been long sought but thus far have eluded those skilled in the art.